#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include "algorithm.h"
/**
 * @brief  算法接口
 * @param  input            输入参数
 * @param  output           输出参数
 * @return int32_t          返回成功或者失败，RETURN_OK 或 RETURN_ERROR
 */
 /*快排函数*/
void sort_eboc(IOUint * a,int32_t l,int32_t r){
    srand(time(NULL));
    int32_t  mid=l+rand()%(r-l+1);
    int32_t  i=l,j=r;
    IOUint t=a[mid];
    a[mid]=a[i];
    a[i]=t;
    while(i<j){
        while (a[j].startLpos>t.startLpos && j>i) j--;
        if (i<j) {a[i]=a[j];i++;}  
        while (a[i].startLpos<t.startLpos && j>i) i++;
        if (i<j) {a[j]=a[i];j--;}  
    }
    a[i]=t;
    if (l<j-1) sort_eboc(a,l,j-1);
    if (r>i+1) sort_eboc(a,i+1,r);
}

//能量不足的时候不要开启一个具有挑战性的对话
//理论意识是一种“类”意识
//从论域到论题——题目不要太大
//时空限定、类型分割、方法选择
void repub(int32_t x,int32_t y,OutputParam *output, OutputParam *newo){//将原x位置的IO移到y位置
    int32_t l=output->len;
    if (x==y) return;
    if (x<y) {
        for(int32_t i=0;i<x;i++) newo->sequence[i]=output->sequence[i];
        for(int32_t i=x;i<y;i++) newo->sequence[i]=output->sequence[i+1];
        newo->sequence[y]=output->sequence[x];
        for(int32_t i=y+1;i<l;i++) newo->sequence[i]=output->sequence[i];
    }
    else{
        for(int32_t i=0;i<y;i++) newo->sequence[i]=output->sequence[i];
        newo->sequence[y]=output->sequence[x];
        for(int32_t i=y;i<x;i++) newo->sequence[i+1]=output->sequence[i];
        for(int32_t i=x+1;i<l;i++) newo->sequence[i]=output->sequence[i];
    }
}
/*计算插入增加的寻道时间*/
int32_t insert_cost(int32_t x,int32_t y,const InputParam *input,int32_t *a){
    int32_t cost=0;
    HeadInfo start,end;
    if (x>0) {
        start.wrap=input->ioVec.ioArray[a[x-1]-1].wrap;
        start.lpos=input->ioVec.ioArray[a[x-1]-1].endLpos;
        start.status=HEAD_RW;
        end.wrap=input->ioVec.ioArray[a[y]-1].wrap;
        end.lpos=input->ioVec.ioArray[a[y]-1].startLpos;
        end.status=HEAD_RW;
        cost+=SeekTimeCalculate(&start, &end);
    }
    if (x==0){
        start=input->headInfo;
        end.wrap=input->ioVec.ioArray[a[y]-1].wrap;
        end.lpos=input->ioVec.ioArray[a[y]-1].startLpos;
        end.status=HEAD_RW;
        cost+=SeekTimeCalculate(&start, &end);
    }
    if (x<input->ioVec.len) {
        start.wrap=input->ioVec.ioArray[a[y]-1].wrap;
        start.lpos=input->ioVec.ioArray[a[y]-1].endLpos;
        start.status=HEAD_RW;
        end.wrap=input->ioVec.ioArray[a[x]-1].wrap;
        end.lpos=input->ioVec.ioArray[a[x]-1].startLpos;
        end.status=HEAD_RW;
        cost+=SeekTimeCalculate(&start, &end);
    }
    if (x>0 && x<input->ioVec.len) {
        start.wrap=input->ioVec.ioArray[a[x-1]-1].wrap;
        start.lpos=input->ioVec.ioArray[a[x-1]-1].endLpos;
        start.status=HEAD_RW;
        end.wrap=input->ioVec.ioArray[a[x]-1].wrap;
        end.lpos=input->ioVec.ioArray[a[x]-1].startLpos;
        end.status=HEAD_RW;
        cost-=SeekTimeCalculate(&start, &end);
    }
    if (x==0 && x<input->ioVec.len) {
        start=input->headInfo;
        end.wrap=input->ioVec.ioArray[a[x]-1].wrap;
        end.lpos=input->ioVec.ioArray[a[x]-1].startLpos;
        end.status=HEAD_RW;
        cost-=SeekTimeCalculate(&start, &end);
    }
    return cost;
}
//计算原位置需要的寻道时间-连接后的寻道时间
int32_t delete_cost(int32_t x,const InputParam *input,int32_t *a){
    int32_t cost=0;
    HeadInfo start,end;
    if (x>0) {
        start.wrap=input->ioVec.ioArray[a[x-1]-1].wrap;
        start.lpos=input->ioVec.ioArray[a[x-1]-1].endLpos;
        start.status=HEAD_RW;
        end.wrap=input->ioVec.ioArray[a[x]-1].wrap;
        end.lpos=input->ioVec.ioArray[a[x]-1].startLpos;
        end.status=HEAD_RW;
        cost+=SeekTimeCalculate(&start, &end);
    }
    if (x==0){
        start=input->headInfo;
        end.wrap=input->ioVec.ioArray[a[x]-1].wrap;
        end.lpos=input->ioVec.ioArray[a[x]-1].startLpos;
        end.status=HEAD_RW;
        cost+=SeekTimeCalculate(&start, &end);
    }
    if (x<input->ioVec.len-1) {
        start.wrap=input->ioVec.ioArray[a[x]-1].wrap;
        start.lpos=input->ioVec.ioArray[a[x]-1].endLpos;
        start.status=HEAD_RW;
        end.wrap=input->ioVec.ioArray[a[x+1]-1].wrap;
        end.lpos=input->ioVec.ioArray[a[x+1]-1].startLpos;
        end.status=HEAD_RW;
        cost+=SeekTimeCalculate(&start, &end);
    }
    if (x>0 && x<input->ioVec.len-1) {
        start.wrap=input->ioVec.ioArray[a[x-1]-1].wrap;
        start.lpos=input->ioVec.ioArray[a[x-1]-1].endLpos;
        start.status=HEAD_RW;
        end.wrap=input->ioVec.ioArray[a[x+1]-1].wrap;
        end.lpos=input->ioVec.ioArray[a[x+1]-1].startLpos;
        end.status=HEAD_RW;
        cost-=SeekTimeCalculate(&start, &end);
    }
    if (x==0 && x<input->ioVec.len-1) {
        start=input->headInfo;
        end.wrap=input->ioVec.ioArray[a[x+1]-1].wrap;
        end.lpos=input->ioVec.ioArray[a[x+1]-1].startLpos;
        end.status=HEAD_RW;
        cost-=SeekTimeCalculate(&start, &end);
    }
    return cost;
}
/*计算交换后的花费*/
int32_t swap_cost(int32_t x,int32_t y,const InputParam *input,int32_t *a){
    int32_t cost=0;
    HeadInfo start,end;
    if (x>0) {
        start.wrap=input->ioVec.ioArray[a[x-1]-1].wrap;
        start.lpos=input->ioVec.ioArray[a[x-1]-1].endLpos;
        start.status=HEAD_RW;
        end.wrap=input->ioVec.ioArray[a[y]-1].wrap;
        end.lpos=input->ioVec.ioArray[a[y]-1].startLpos;
        end.status=HEAD_RW;
        cost+=SeekTimeCalculate(&start, &end);
    }
    if (x==0){
        start=input->headInfo;
        end.wrap=input->ioVec.ioArray[a[y]-1].wrap;
        end.lpos=input->ioVec.ioArray[a[y]-1].startLpos;
        end.status=HEAD_RW;
        cost+=SeekTimeCalculate(&start, &end);
    }
    if (x<input->ioVec.len-1) {
        start.wrap=input->ioVec.ioArray[a[y]-1].wrap;
        start.lpos=input->ioVec.ioArray[a[y]-1].endLpos;
        start.status=HEAD_RW;
        end.wrap=input->ioVec.ioArray[a[x+1]-1].wrap;
        end.lpos=input->ioVec.ioArray[a[x+1]-1].startLpos;
        end.status=HEAD_RW;
        cost+=SeekTimeCalculate(&start, &end);
    }
    if (x==input->ioVec.len-1){
        start.wrap=input->ioVec.ioArray[a[y]-1].wrap;
        start.lpos=input->ioVec.ioArray[a[y]-1].endLpos;
        start.status=HEAD_RW;
        end.wrap=start.wrap;
        if (end.wrap%2==0) end.lpos=MAX_LPOS;
        else end.lpos=0;
        end.status=HEAD_RW;
        cost+=SeekTimeCalculate(&start, &end);
    }
    return cost;
}
/*插入更新后的位置*/

void insert_seq(int32_t y,int32_t x,int32_t l,int32_t *a){
    if (x==y) return;
    if (x<y) {
        int32_t t=a[x];
        for(int32_t i=x;i<y-1;i++) a[i]=a[i+1];
        a[y-1]=t;
    }
    else{
        int32_t t=a[x];
        for(int32_t i=x;i>y;i--) a[i]=a[i-1];
        a[y]=t;
    }

}
/*交换序列对应位置*/ 
void swap(int32_t x,int32_t y,int32_t *a ){
    int32_t p;
    p=a[x];a[x]=a[y];a[y]=p;
}
/*指数函数*/
double expe(double x)
{
    int32_t T=8;
    x = 1.0 + x/256;
    while(T--) x *= x;
    return x;
}
/*调试函数*/
void print_eboc(IOVector eb){
    printf("wrap kind %d sort :\n",eb.ioArray[0].wrap%2);
    for(int32_t i=0;i<eb.len;i++){
        printf("\t%u\n",eb.ioArray[i].startLpos);
    }
}

int32_t max(int32_t a,int32_t b){
    return a>b?a:b;
}
int32_t min(int32_t a,int32_t b){
    return a<b?a:b;
}
/************/

int32_t IOScheduleAlgorithm(const InputParam *input, OutputParam *output)
{
    int32_t ret,signal;
    HeadInfo thead={input->headInfo.wrap,input->headInfo.lpos,input->headInfo.status };
    /* 算法：scan */
    output->len = input->ioVec.len;
    /*sort part*/
    ID* D=(ID*)malloc(output->len*sizeof(ID));
    IOVector eboc[2];
    eboc[0].ioArray= (IOUint *)malloc(output->len * sizeof(IOUint));
    eboc[0].len=0;
    eboc[1].ioArray= (IOUint *)malloc(output->len * sizeof(IOUint));
    eboc[1].len=0;
    for (uint32_t i = 0; i < output->len; i++) {
        signal=input->ioVec.ioArray[i].wrap%2;
        eboc[signal].ioArray[eboc[signal].len]=input->ioVec.ioArray[i];
        eboc[signal].len++;
    }
    sort_eboc(eboc[0].ioArray,0,eboc[0].len-1);
    sort_eboc(eboc[1].ioArray,0,eboc[1].len-1);
    //print_eboc(eboc[0]);print_eboc(eboc[1]);
    dnode hd[2],p,q;
    hd[0]=(dnode)malloc(sizeof(dNode));hd[1]=(dnode)malloc(sizeof(dNode));
    hd[0]->next=NULL;
    p=hd[0];
    for(int32_t i=0;i<eboc[0].len;i++){
        q=(dnode)malloc(sizeof(dNode));
        q->data=i;q->next=NULL;
        p->next=q;p=q;
    }
    p=hd[1];
    p->next=NULL;
    for(int32_t i=0;i<eboc[1].len;i++){
        q=(dnode)malloc(sizeof(dNode));
        q->data=i;q->next=p->next;
        p->next=q;
    }
    int32_t l=0;
    while (l<input->ioVec.len) {  
        p=hd[0];q=hd[0]->next; 
        while(q){
            while(q &&
            eboc[0].ioArray[q->data].startLpos<=thead.lpos) {
                p=q;
                q=q->next;
            }
            if (q){
                output->sequence[l]=eboc[0].ioArray[q->data].id;
                D[l].b=0;D[l].daid=q->data;
                l++;
                thead.lpos=eboc[0].ioArray[q->data].endLpos;
                p->next=q->next;
                free(q);
                q=p->next;
            }
        }  
        thead.lpos=MAX_LPOS;
        p=hd[1];q=hd[1]->next; 
        while(q){
            while(q &&
            eboc[1].ioArray[q->data].startLpos>=thead.lpos) {
                p=q;
                q=q->next;
            }
            if (q){
                output->sequence[l]=eboc[1].ioArray[q->data].id;
                D[l].b=1;D[l].daid=q->data;
                l++;
                thead.lpos=eboc[1].ioArray[q->data].endLpos;
                p->next=q->next;
                free(q);
                q=p->next;
            }
        }
        thead.lpos=0;
    }

    AccessTime accessTime0 = {0};
    TotalAccessTime(input, output, &accessTime0);
    uint32_t seekT0=accessTime0.addressDuration;
    uint32_t seekTmin=seekT0;
    printf("seekT0:%u ms\n",seekT0);
    /*基于scan开始模拟退火过程*/
    OutputParam *o1=(OutputParam*)malloc(sizeof(OutputParam));
    o1->sequence=(uint32_t*)malloc(l*sizeof(uint32_t));
    o1->len=l;
    for(int32_t i=0;i<l;i++){
        o1->sequence[i]=output->sequence[i];
    }
    OutputParam *re=(OutputParam*)malloc(sizeof(OutputParam));
    re->sequence=(uint32_t*)malloc(l*sizeof(uint32_t));
    re->len=l;
    for(int32_t i=0;i<l;i++){
        re->sequence[i]=output->sequence[i];
    }
    int32_t cntSA=10000/l;
    if (cntSA<=1) cntSA+=1;
    if (cntSA>100) cntSA=150;
    if (cntSA>500) cntSA=100;
        double T=200000,endT=0.1,startT=200000;
        int32_t cntti=0;
        double d=0.98;
        for(int32_t i=0;i<l;i++){
            output->sequence[i]=re->sequence[i];
        }
        while(T>endT){
            srand(T*time(NULL)*100000);

            int32_t x[6];
            int32_t cntx=min(6,l/5);
            for(int32_t i=0;i<cntx;i++){
                int32_t flag=0;
                do{
                    flag=0;
                    x[i]=rand()%l;
                    for(int32_t j=0;j<i;j++){
                        if (x[i]==x[j]) {
                            flag=1;
                            break;
                        }
                    }
                }while(flag);
            }

            /* 插入优化*/
            int32_t costi,costy;   
            for(int32_t j=0;j<cntx;j++){     
                int32_t y=x[j];  
                costy=delete_cost(y,input,output->sequence);
                for(int32_t i=0;i<l;i++){
                    if (i!=x[j]+1 && i!=x[j] && i!=x[j]-1){ 
                        costi=insert_cost(i,x[j],input,output->sequence);
                        if (costy>costi) {
                            costy=costi;
                            y=i;

                        }
                    }
                }
                insert_seq(y,x[j],output->len,output->sequence);

            }
            AccessTime accessTime = {0};
            TotalAccessTime(input, output, &accessTime);
            uint32_t seekTnow=accessTime.addressDuration;
            if (seekTnow<seekTmin){
                seekTmin=seekTnow;
                for(int32_t i=0;i<l;i++){
                    o1->sequence[i]=output->sequence[i];
                }
            }
            T=T*d;
        }
    /*正式退火*/
    while(cntSA--){
        double T=200000,endT=0.1,startT=200000;
        int32_t cntti=0;
        double d=0.98;
        for(int32_t i=0;i<l;i++){
            output->sequence[i]=re->sequence[i];
        }
        while(T>endT){
            srand(T*time(NULL)*(cntSA+1)*100000);

            int32_t s[200]={0};
            int32_t cnts=min(200,l/5*2);
            int32_t cost1=0,cost2=0;
            AccessTime accessTime1 = {0};
            TotalAccessTime(input, output, &accessTime1);
            cost1=accessTime1.addressDuration;
            for(int32_t i=0;i<cnts;i++){
                do{
                    s[i]=rand()%l;
                    for(int32_t j=0;j<i;j++){
                        if (s[i]==s[j]) {
                            s[i]=-1;
                            break;
                        }
                    }
                }while(s[i]==-1);
            }
            
            for(int32_t i=0;i<cnts/2;i++){
                int32_t x=s[i];
                int32_t y=s[cnts/2+i];
                swap(x,y,output->sequence);
            }   
            AccessTime accessTime2 = {0};
            TotalAccessTime(input, output, &accessTime2);
            cost2=accessTime2.addressDuration;

            if (cost2>=cost1){
                srand(T*time(NULL)*(cntSA+1)*100000);
                double p=expe(((double)(cost1-cost2))/T);
                int32_t zp=(int32_t)p*10000000;
                int32_t ra=rand()%10000000;
                if (zp<ra) {
                    for(int32_t i=0;i<cnts/2;i++){
                        int32_t x=s[i];
                        int32_t y=s[cnts/2+i];
                        swap(x,y,output->sequence);
                    }
                } 
            }

            int32_t x[6];
            int32_t cntx=min(6,l/5);
            for(int32_t i=0;i<cntx;i++){
                int32_t flag=0;
                do{
                    flag=0;
                    x[i]=rand()%l;
                    for(int32_t j=0;j<i;j++){
                        if (x[i]==x[j]) {
                            flag=1;
                            break;
                        }
                    }
                }while(flag);
            }
            int32_t costi,costy;   
            for(int32_t j=0;j<cntx;j++){     
                int32_t y=x[j];  
                costy=delete_cost(y,input,output->sequence);
                for(int32_t i=0;i<l;i++){
                    if (i!=x[j]+1 && i!=x[j] && i!=x[j]-1){ 
                        costi=insert_cost(i,x[j],input,output->sequence);
                        if (costy>costi) {
                            costy=costi;
                            y=i;
                        }
                    }
                }
                insert_seq(y,x[j],output->len,output->sequence);
            }
            AccessTime accessTime = {0};
            TotalAccessTime(input, output, &accessTime);
            uint32_t seekTnow=accessTime.addressDuration;
            if (seekTnow<seekTmin){
                seekTmin=seekTnow;
                for(int32_t i=0;i<l;i++){
                    o1->sequence[i]=output->sequence[i];
                }
            }
            T=T*d;
        }
    }
    for(int32_t i=0;i<l;i++){
        output->sequence[i]=o1->sequence[i];
    }
    /* 释放内存 */
    free(D);
    free(o1->sequence);
    free(o1);
    free(eboc[0].ioArray);
    free(eboc[1].ioArray);
    free(hd[0]);free(hd[1]);
    return RETURN_OK;
}

/**
 * @brief  算法运行的主入口
 * @param  input            输入参数
 * @param  output           输出参数
 * @return uint32_t          返回成功或者失败，RETURN_OK 或 RETURN_ERROR
 */
int32_t AlgorithmRun(const InputParam *input, OutputParam *output)
{
    int32_t ret;

    ret = IOScheduleAlgorithm(input, output);

    return RETURN_OK;
}
